package org.example;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

//leetcode 239 滑动窗口最大值 https://leetcode.cn/problems/sliding-window-maximum/description/

/**
 * 通过单调队列，当要加入队列的值大于队列尾部的值时就将队列尾部的小于该值的都移除，保证对头都是当前窗口内的最大值
 * 由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 iii 和 jjj，其中 iii 在 jjj 的左侧（i<ji < ji<j），并且 iii 对应的元素不大于 jjj 对应的元素（nums[i]≤nums[j]\textit{nums}[i] \leq \textit{nums}[j]nums[i]≤nums[j]），那么会发生什么呢？
 *
 * 当滑动窗口向右移动时，只要 iii 还在窗口中，那么 jjj 一定也还在窗口中，这是 iii 在 jjj 的左侧所保证的。因此，由于 nums[j]\textit{nums}[j]nums[j] 的存在，nums[i]\textit{nums}[i]nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i]\textit{nums}[i]nums[i] 永久地移除。
 */
class Solution {
    Deque<Integer> deque;

    public void add(int n) {
        while (!deque.isEmpty() && n > deque.getLast()) deque.removeLast();
        deque.add(n);
    }

    public int getMax() {
        return deque.peek();
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        deque = new ArrayDeque<>();
        int n = nums.length, index = 0;
        int[] ret = new int[k > n ? 1 : n - k + 1];
        for (int i = 0; i < k; i++) add(nums[i]);
        ret[index++] = getMax();
        for (int i = 0; i < n - k; i++) {
            if (nums[i] == getMax()) deque.poll();
            add(nums[i + k]);
            ret[index++] = getMax();
        }
        return ret;
    }
}
public class Test1 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, index = 0;
        int[] ret = new int[k > n ? 1 : n - k + 1];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < k; i++) priorityQueue.add(nums[i]);
        ret[index++] = priorityQueue.peek();
        for (int i = 0; i < n - k; i++) {
            priorityQueue.remove(nums[i]);
            priorityQueue.add(nums[i + k]);
            ret[index++] = priorityQueue.peek();
        }
        return ret;
    }
    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] arr = {9,10,9,-7,-4,-8,2,-6};
        test1.maxSlidingWindow(arr,5);
        System.out.println(444);
    }
}
